package com.atguigu.gulimall.cart.config;

import java.util.Arrays;

public class test {
    public static void main(String[] args) {
        int arr[] = {32, 45, 18, 1,3,46,79,13,4,0};
        xierSort2(arr);
    }

    /**
     * 希尔交换排序
     * @param arr
     * 1.首先数组长度除以2 一直到1为止 length/2
     * 2.每次除以二之后封装成一个独立的数组 [arr[0],arr[length/2]
     *
     */
    public static void xierSort(int arr[]){
        int temp = 0;
        for (int gap = arr.length/2;gap>0;gap/=2){
            for (int i = gap;i<arr.length;i++)
            for (int j=i-gap;j>=0;j-=gap){
                if (arr[j]>arr[gap+j]){
                    temp=arr[j];
                    arr[j] = arr[gap+j];
                    arr[gap+j] = temp;
                }

            }
            System.out.println(Arrays.toString(arr));
        }
    }

    /**
     * 希尔排序移位法  移位法  先设置一个辅助变量 把第一位交给辅助变量 如果移位的话 则把下一位值赋给第一位 元素下标改动 然后把辅助变量的值给移位的
      * @param arr
     */
    public static void xierSort2(int arr[]){
        int temp = 0;
        for (int gap = arr.length/2;gap>0;gap/=2){
            for (int i = gap;i<arr.length;i++){
               int j = i; //第一个元素的下标
               temp = arr[j]; //第一个元素
                if(arr[j]<arr[j-gap]){
                    while (j-gap>=0&&temp<arr[j-gap]) {
                        arr[j] = arr[j - gap];
                        j -= gap;
                    }
                    arr[j] = temp;
                }
            }
            System.out.println(Arrays.toString(arr));
        }
    }
    /**
     * 选择排序
     * @param arr
     */
    public void sort(int arr[]){
        //选择排序
        for (int i = 0;i<arr.length-1;i++){
            int min = arr[i]; //首先加入arr【0】为最小值
            int minIndex = i;
            for (int j = i+1;j<arr.length;j++){
                if (min>arr[j]){
                    min = arr[j]; //第一次选择排序最小值
                    minIndex = j;//第一次排序最下值在那个下标
                }
            }
            arr[minIndex] = arr[i];
            arr[i] =min;
        }
        System.out.println(Arrays.toString(arr));
    }

}
